# 存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除链表中所有存在数字重复情况的节点，只保留原始链表中 没有重复出现 的数字。
#  返回同样按升序排列的结果链表。
#
#  示例 1：
# 输入：head = [1,2,3,3,4,4,5]
# 输出：[1,2,5]
#
#  示例 2：
# 输入：head = [1,1,1,2,3]
# 输出：[2,3]
import math

from com.example.linked.common import *


class Solution:
    def deleteDuplicates2(self, head: ListNode) -> ListNode:
        """
        单个指针逐个删除相邻重复的元素
        :param head:
        :return:
        """
        if not head or not head.next:
            return head

        # 链表的头节点可能会被删除，因此引入一个没有意义的头结点指向链表的开始节点
        newHead = ListNode(0, head)

        cur = newHead
        while cur.next and cur.next.next:
            # 如果当前 cur.next 与 cur.next.next 对应的元素相同，就将 cur.next 以及所有后面拥有相同元素值的链表节点全部删除
            if cur.next.val == cur.next.next.val:
                x = cur.next.val
                while cur.next and cur.next.val == x:
                    cur.next = cur.next.next
            else:
                cur = cur.next

        return newHead.next

    def deleteDuplicates1(self, head: ListNode) -> ListNode:
        """
        双指针
        为了可以删除与开始结点相同的元素需要引入没有意义的头结点
        left指针指向的是已经处理的链表元素
        right为当前遍历的元素
        :param head:
        :return:
        """
        if not head or not head.next:
            return head
        newHead = ListNode(math.inf)
        newHead.next = head
        left, right = newHead, head
        while right:
            if right.next and right.val == right.next.val:  # 当当前遍历的节点和下一节点相同时，1.right一直后移，直至相邻两个节点不同为止
                while right.next and right.val == right.next.val:
                    right = right.next
                # 2.将整段重复的节点删除
                left.next = right.next
                right = right.next
            else:  # 相邻节点不同则两个指针都后移一步
                left = left.next
                right = right.next

        return newHead.next

    def deleteDuplicates(self, head: ListNode) -> ListNode:
        return self.deleteDuplicates2(head)


if __name__ == "__main__":
    # lst = [1, 1, 1, 2, 3]
    head = getListNode(1, 2, 3, 3, 4, 4, 4, 5)
    res = Solution().deleteDuplicates(head.next)
    vistListNode(res)
